package Hot100;

import common.TreeNode;

/**
 * @author zhangmin
 * @create 2022-01-14 14:42
 */
public class convertBST538 {
    /**
     * 538. 把二叉搜索树转换为累加树
     * 给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），
     * 使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。
     * 递归，先处理右子树再处理根节点，最后处理左子树
     * */
    int sum=0;
    void traverse(TreeNode root){
        if (root==null) return;
        //处理右子树
        traverse(root.right);
        //处理根节点
        sum+=root.val;
        root.val=sum;
        //处理左子树
        traverse(root.left);
    }
    public TreeNode convertBST(TreeNode root) {
        traverse(root);
        return root;
    }
}
